package com.markus.code.top100;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/19 21:57
 * todo: 寻找两个正序数组的中位数(未做出)
 */
public class LeetCode4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //这一步的操作主要是让上面的数组为短的，下面的数组为长的
        if (nums1.length > nums2.length){
            int []temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;
        //求出两个数组的长度的一半，这个式子主要解决：如果两个数组长度和为奇数，
        //那么前一半数组的长度就会比后一半数组长度多1个，偶数的话，两边均分
        int totalLeft = (m+n+1)>>1;
        //在上面数组的区间[0...m]找出恰当的分割线
        //条件：nums1[i-1] <= nums2[j] && nums1[i] >= nums2[j-1]
        int left = 0;
        int right = m;
        while (left < right){
            //计算出上面数组的分割线
            //为什么是这样一个公式：当right-left为奇数的时候，向上取整。保证i-1不越界
            int i = left + (right-left+1)/2;
            //得出下面数组的分割线
            int j = totalLeft-i;
            if (nums1[i-1] > nums2[j]){
                //下次遍历应该从[left...i-1]找出恰当的分割线
                right = i-1;
            }else{
                //否则下次遍历应该从[i...right]找出恰当的分割线
                left = i;
            }
        }
        int i = left;
        int j = totalLeft-i;
        int leftNums1Max = i==0?Integer.MIN_VALUE:nums1[i-1];
        int rightNums1Min = i==m?Integer.MAX_VALUE:nums1[i];
        int leftNums2Max = j==0?Integer.MIN_VALUE:nums2[j-1];
        int rightNums2Min = j==n?Integer.MAX_VALUE:nums2[j];
        return (m+n)%2==0?(Math.max(leftNums1Max,leftNums2Max)+Math.min(rightNums1Min,rightNums2Min))*0.5:
                Math.max(leftNums1Max,leftNums2Max);
    }

    public static void main(String[] args) {
        int nums1[] = {1,2};
        int nums2[] = {3,4};
        LeetCode4 demo = new LeetCode4();
        System.out.println(demo.findMedianSortedArrays(nums1,nums2));
    }
}
